package org.example.code.test2024.nine_mouth;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class test0912 {

//    public int maxProfit(int[] prices) {
//        int n = prices.length;
//        int max = 0;
//        for (int i = 0; i < n; i++) {
//            for(int j=i+1;j<n;j++){
//                if(prices[j]>prices[i]){
//                    max = Math.max(max,prices[j]-prices[i]);
//                }
//            }
//        }
//        return max;
//    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int max = 0;
        int min = prices[0];
        for (int i = 0; i < n; i++) {
            if(prices[i] < min)
                min = prices[i];
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int max = 0;
        for(int i = 0; i < n; i++) {
            if(i>max){
                return false;
            }
            max = Math.max(max, nums[i] + i);
            if(max>=n-1){
                return true;
            }
        }
        return false;
    }

    public int jump(int[] nums) {
        int n = nums.length;
        int max = 0;
        int curMax = 0;
        int sum =0;
        for(int i = 0; i < n; i++) {
            if(i==n-1){
                break;
            }
            curMax = Math.max(curMax, nums[i] + i);
            if(i==max){
                max = curMax;
                sum++;
            }
        }
        return sum;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<Integer>();
        int[] last = new int[26];
        for(int i=0;i<s.length();i++){
            last[s.charAt(i)-'a']=i;
        }
        int end = 0,start = 0;
        for(int i=0;i<s.length();i++){
            end = Math.max(end, last[s.charAt(i)-'a']);
            if(i==end){
                res.add(end-start+1);
                start=i+1;
            }
        }
        return res;
    }

    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        if(n==0){
            return 0;
        }
        if(n<2){
            return 1;
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

//    public List<List<Integer>> generate(int numRows) {
//        List<List<Integer>> res = new ArrayList<>();
//        if(numRows==0){
//            return res;
//        }
//        int[][] result = new int[numRows][numRows];
//        for(int i=0;i<numRows;i++){
//            result[numRows-1][i]=1;
//            result[i][0]=1;
//        }
//        for(int i=0;i<numRows;i++){
//            for(int j=0;j<numRows;j++){
//                if(i==j){
//                    result[i][j]=1;
//                }
//            }
//        }
//        for(int i=0;i<numRows;i++) {
//            for (int j = 0; j < numRows; j++) {
//                if((i-1)>=0&&(j-1)>=0&&result[i][j-1]>0&&result[i-1][j-1]>0){
//                    result[i][j] = result[i-1][j-1]+result[i-1][j];
//                }
//            }
//        }
//        for(int i=0;i<numRows;i++) {
//            List<Integer> list = new ArrayList<>();
//            for (int j = 0; j < numRows; j++) {
//                if(result[i][j]>0){
//                    list.add(result[i][j]);
//                }
//            }
//            res.add(list);
//        }
//        return res;
//    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<numRows;i++){
            List<Integer> row = new ArrayList<>();
            for(int j=0;j<i+1;j++){
                if(j==0||j==i){
                    row.add(1);
                }else{
                    row.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
                }
            }
            res.add(row);
        }
        return res;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i=2;i<n;i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }

    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j*j<=i;j++){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=1;i<=amount;i++){
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }


    public static void main(String[] args) {
        test0912 test = new test0912();
        int[] nums = {1,2,5};
        System.out.println(test.coinChange(nums,11));
    }
}
